class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
     if(root == NULL) return root;
     if(root->val == key){
       if(root->left && root->right){
        TreeNode* cur = root->right;
        while(cur->left != NULL){
          cur = cur->left;
        }
        cur->left = root->left;
        return root->right;
       }else if(root->left && !root->right){
         return root->left;
       }else if(root->right && !root->left){
         return root->right;
       }else{
         return NULL;
       }
     }
     if(root->val > key){
       root->left = deleteNode(root->left,key);
     }
     if(root->val < key){
       root->right = deleteNode(root->right,key);
     }
     return root;
    }
};
